「CSP-S 2025」复盘

T1

沉痛悼念5位学长考场上降智没写出来T1正解

首先因为它规定了$n$为偶数，并且一组最多有$\frac{n}{2}$个数，所以可以很自然的可以想到一个性质：对于每个人要么选最大值要么选次大值

然后某位SB考场上想到这个东西Olympiad in Programming and Sports直接写了一坨反悔贪心上去(不愧是我)

但是根本没必要这么麻烦，只需要先不管人数限制，在把多余的人中更改后减少的贡献较少的分到另一组即可，优先队列$O(nlog(n))$可以解决

对于大佬，也有一种更高级的算法(具体名字忘了)可以$O(n)$过本题，感兴趣的可以上网搜索

Details

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define reg register

const int N=1e5+10;

struct cmp
{
    int big, nbig;

    bool operator< ( const cmp &a )const
    {
        return big-nbig > a.big-a.nbig;
    }

};

struct node
{
    int val, idx;

    bool operator< ( const node &a )const
    {
        return val > a.val;
    }

}a[N][4];



void sovel()
{
    int n;
    cin>>n;
    priority_queue< cmp > pq[4];
    for( int i=1;i<=n;i++ )
    {
        for( int j=1;j<=3;j++ )
            cin>>a[i][j].val, a[i][j].idx=j;
        sort( a[i]+1,a[i]+3+1 );
        pq[a[i][1].idx].push( { a[i][1].val,a[i][2].val } );
    }
    int ans=0;
    for( int i=1;i<=3;i++ )
        while( !pq[i].empty() )
            if( pq[i].size() > n/2 ) ans+=pq[i].top().nbig, pq[i].pop();
            else ans+=pq[i].top().big, pq[i].pop();
    cout<<ans<<"\n";
}

int main()
{
    // freopen( "club.in","r",stdin );
    // freopen( "club.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ), cout.tie( nullptr );
    int t;
    for( cin>>t;t;t-- ) sovel(); 
    QWQ
}

T2

沉痛悼念自己考场上想到正解以为复杂度有问题没有写，也再次提醒大家，如今的$CCF$的少爷机已经可以一秒跑$2e9$~$3e9$了QAQ

首先先不考虑进行任何的城市化改造，本题就是一个简单的最小生成树模版，把加入最小生成树的边记录下来

再考虑进行城市化改造

因为$k\leqslant 10$，所以我们可以暴力枚举(没错，就是$O(2^k)$枚举)，然后建出新图进行最小生成树求解

易得如果我们还要选择原本的边的话，选择原最小生成树的树边一定最优，这样多次求解最小生成树求最优解便可$AC$本题

使用$Kruskal$复杂度为$O(mlog(m)+2^k\times nklog(nk))=1.7e9$，$Prim$复杂度为$O(nlog(n)+2^k\times (n+k)log(n+k))=1.3e8$，均可通过本题

Details

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define reg register

const int N=1e4+1e1+10;
const ll inf=1e18;

struct edge
{
    int u, v, w;

    bool operator< ( const edge &a )const
    {
        return w > a.w;
    }

}use[N];

int n, k;
int fa[N], c[11];
int rode[11][N];

inline int get( int x ){ return ( fa[x] == x ? x : fa[x]=get( fa[x] ) ); }
inline void merge( int x,int y ){ fa[get( x )]=get( y ); }
inline void intt(){ for( int i=1;i<=n+k;i++ ) fa[i]=i; }

int main()
{
//    freopen( "road.in","r",stdin );
//    freopen( "road.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ), cout.tie( nullptr );
    int m;
    cin>>n>>m>>k;
    priority_queue< edge > pq;
    for( int i=1, u, v, w;i<=m;i++ )
    {
        cin>>u>>v>>w;
        pq.push( { u,v,w } );
    }
    intt();
    int cnt=1;
    while( cnt < n )
    {
        auto [u,v,w]=pq.top();
        pq.pop();
        if( get( u ) == get( v ) ) continue;
        use[cnt++]={ u,v,w };
        merge( u,v );
    }
    for( int i=1;i<=k;i++ )
    {
        cin>>c[i];
        for( int j=1;j<=n;j++ ) cin>>rode[i][j];
    }
    ll ans=inf;
    for( int state=0;state<( 1<<k );state++ )
    {
        int tmp=n;
        ll tans=0;
        priority_queue< edge > pq;
        for( int i=0;i<k;i++ )
            if( ( state>>i )&1 )
            {
                tmp++;
                tans+=c[i+1];
                for( int j=1;j<=n;j++ )
                    pq.push( { n+i+1,j,rode[i+1][j] } );  
            }
        for( int i=1;i<n;i++ ) pq.push( use[i] );
        int cnt=1;
        intt();
        while( cnt < tmp )
        {
            auto [u,v,w]=pq.top();
            pq.pop();
            if( get( u ) == get( v ) ) continue;
            cnt++;
            merge( u,v );
            tans+=w;
        }
        ans=min( ans,tans );
    }
    cout<<ans;
    QWQ
}

T3

论CCF在提高级放这道题的意味：何意味？

虽然存在提高级算法的方法，但是hash+树状数组+扫描线无论是时间，空间以及实现难度上都十分的高

这里蒟蒻暂时不会本题，先丢一份AI的代码吧(AC自动机)

Details

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

const int ALPHABET_SIZE = 26;

struct TrieNode {
    TrieNode* children[ALPHABET_SIZE];
    unordered_map<int, vector<pair<string, int>>> patterns; // length -> (pattern, count)
    TrieNode* fail;
    
    TrieNode() {
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            children[i] = nullptr;
        }
        fail = nullptr;
    }
};

void insertTrie(TrieNode* root, const string& pattern, const string& replacement, int count) {
    TrieNode* node = root;
    for (char c : pattern) {
        int index = c - 'a';
        if (!node->children[index]) {
            node->children[index] = new TrieNode();
        }
        node = node->children[index];
    }
    int len = pattern.length();
    node->patterns[len].emplace_back(replacement, count);
}

void buildFailureLinks(TrieNode* root) {
    queue<TrieNode*> q;
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
        if (root->children[i]) {
            root->children[i]->fail = root;
            q.push(root->children[i]);
        } else {
            root->children[i] = root;
        }
    }
    
    while (!q.empty()) {
        TrieNode* current = q.front();
        q.pop();
        
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            if (current->children[i]) {
                TrieNode* next = current->children[i];
                TrieNode* temp = current->fail;
                
                while (!temp->children[i]) {
                    temp = temp->fail;
                }
                
                next->fail = temp->children[i];
                q.push(next);
            }
        }
    }
}

long long query(TrieNode* root, const string& text, const string& target) {
    long long count = 0;
    int n = text.size();
    int m = target.size();
    if (n != m) return 0;
    
    vector<int> lcp(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        if (text[i] == target[i]) {
            lcp[i] = lcp[i + 1] + 1;
        } else {
            lcp[i] = 0;
        }
    }
    
    vector<int> lcs(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        if (text[i] == target[i]) {
            lcs[i] = (i > 0 ? lcs[i - 1] : 0) + 1;
        } else {
            lcs[i] = 0;
        }
    }
    
    TrieNode* current = root;
    for (int i = 0; i < n; ++i) {
        int index = text[i] - 'a';
        while (!current->children[index]) {
            current = current->fail;
        }
        current = current->children[index];
        
        TrieNode* temp = current;
        while (temp != root) {
            for (auto& [len, repls] : temp->patterns) {
                if (i - len + 1 < 0) continue;
                
                int start = i - len + 1;
                int end = i;
                
                // Check if this replacement is valid
                bool valid = true;
                if (start > 0 && lcs[start - 1] < start) {
                    valid = false;
                }
                if (end < n - 1 && lcp[end + 1] < n - end - 1) {
                    valid = false;
                }
                
                if (valid) {
                    for (auto& [repl, cnt] : repls) {
                        if (target.substr(start, len) == repl) {
                            count += cnt;
                        }
                    }
                }
            }
            temp = temp->fail;
        }
    }
    return count;
}

int main() {
    freopen( "replace.in","r",stdin );
	freopen( "replace.out","w",stdout );

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    TrieNode* root = new TrieNode();
    unordered_map<string, unordered_map<string, int>> patternCount;
    
    for (int i = 0; i < n; ++i) {
        string a, b;
        cin >> a >> b;
        patternCount[a][b]++;
    }
    
    for (const auto& entry : patternCount) {
        const string& pattern = entry.first;
        int totalCount = 0;
        for (const auto& replCount : entry.second) {
            totalCount += replCount.second;
        }
        insertTrie(root, pattern, "", totalCount);
        for (const auto& replCount : entry.second) {
            insertTrie(root, pattern, replCount.first, replCount.second);
        }
    }
    
    buildFailureLinks(root);
    
    for (int i = 0; i < q; ++i) {
        string t1, t2;
        cin >> t1 >> t2;
        cout << query(root, t1, t2) << '\n';
    }
    
    return 0;
}

后记：tmd我成消愁了，T1代码没交对100pts->0pts喜提二等奖